|
In theoretical computer science, in particular in formal language theory, Kleene's algorithm transforms a given deterministic finite automaton (DFA) into a regular expression. Together with other conversion algorithms, it establishes the equivalence of several description formats for regular languages. ==Algorithm description== According to Gross and Yellen (2004),〔 Here: sect.2.1, remark R13 on p.65〕 the algorithm can be traced back to Kleene (1956). This description follows Hopcroft and Ullman (1979).〔 Here: Theorem 2.4, p.33-34〕 Given a deterministic finite automaton ''M'' = (''Q'', Σ, δ, ''q''0, ''F''), with ''Q'' = its set of states, the algorithm computes :the sets ''R'' of all strings that take ''M'' from state ''q''''i'' to ''q''''j'' without going through any state numbered higher than ''k''. Here, "going through a state" means entering ''and'' leaving it, so both ''i'' and ''j'' may be higher than ''k'', but no intermediate state may. Each set ''R'' is represented by a regular expression; the algorithm computes them step by step for ''k'' = -1, 0, ..., ''n''. Since there is no state numbered higher than ''n'', the regular expression ''R'' represents the set of all strings that take ''M'' from its start state ''q''0 to ''q''''j''. If ''F'' = is the set of accept states, the regular expression ''R'' | ... | ''R'' represents the language accepted by ''M''. The initial regular expressions, for ''k'' = -1, are computed as :''R'' = ''a''1 | ... | ''a''''m'' if ''i''≠''j'', where δ(''q''''i'',''a''1) = ... = δ(''q''''i'',''a''''m'') = ''q''''j'' :''R'' = ''a''1 | ... | ''a''''m'' | ε, if ''i''=''j'', where δ(''q''''i'',''a''1) = ... = δ(''q''''i'',''a''''m'') = ''q''''j'' After that, in each step the expressions ''R'' are computed from the previous ones by :''R'' = ''R'' (''R'') * ''R'' | ''R'' 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Kleene's algorithm」の詳細全文を読む スポンサード リンク
|